In many cryptographic protocols, a prover seeks to convince a verifier that he possesses knowledge of a secret or that a certain mathematical relationship holds true. For example, in the Schnorr identification protocol, the prover seeks to demonstrate possession of a secret key corresponding to a specific authenticated public key. By contrast, in a POW, a prover demonstrates to a verifier that he has performed a certain amount of computational work in a specified interval of time. Although not defined as such or treated formally in the literature, POWs have served as the basis for a number of data security applications, including, benchmarking, server access metering, construction of digital time capsules, and protection against spamming and other denial-of-service attacks. A drawback to the use of POWs, however, is the fact that they impose a significant computational load in excess of that associated with many conventional cryptographic protocols.